package com.zto.sch.advance.algorithms.book.grokking;

import com.zto.sch.base.util.CommonUtil;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: sch-diy-parent
 * @description: 二分查找
 * @author: sch
 * @create: 2021-07-08 23:07
 **/
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = CommonUtil.getArray(500000000);
        if (arr.length < 10) {
            System.out.println("源数组：" + Arrays.toString(arr));
        }
        int key = 10;
        int index = findKey(arr, key);
        System.out.println(key + "所有的索引位置是:" + index);
    }

    /**
     * 思路：数组arr,找key,
     * 1，先猜中间的数 arr[mid]。头尾索引：low,high
     * 2，key<arr[mid],high=mid-1;k>arr[mid],low=mid+1; mid=(low+high)>>1
     * 3，重复1~2，直至找到while(low<=hight)
     *
     * @param arr
     * @param key
     * @return
     */
    private static int findKey(int[] arr, int key) {
        int low = 0, high = arr.length - 1, mid = 0;
        while (low <= high) {
            mid = (low + high) >> 1;
            int guess = arr[mid];
            if (guess > key) {
                high = mid - 1;
            } else if (guess < key) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }


    @Test
    public void test() {
        int a = 1;
        System.out.println(a + "::" + (a >> 1));
        System.out.println(Integer.toBinaryString(500000000));
    }

}
